package edu.dgut.bbssystem.tff;

public class Knapsack_Problem01 {
    double maxWeight=100; //背包最大容量
    static int n=5;  //物品的个数
    int[] weight = {10,20,30,40,50}; //第i个物品的重量
    int[] value = {20,30,65,40,60};  //第i个物品的价值
    int currentValue = 0;
    int currentWeight = 0;
    static int[] a = new  int[n]; //记录在树中的移动路径,为1的时候表示选择该组数据，为0的表示不选择该组数据
    static int maxValue = 0;   //背包的最大权重值
    static int[] maxValuePath = new int[n];
    public static void main(String[] args)
    {
        for (int i = 0; i < a.length; i++) {
            a[i]=0;
        }
        Knapsack_Problem01 p = new Knapsack_Problem01();
        p.Search(0,a);
        System.out.println(maxValue);
        for (int i = 0; i < maxValuePath.length; i++) {
            System.out.print(maxValuePath[i]);
        }
    }
    public void Search(int i,int[] a)   //i表示递归深度
    {
        if (i<0){
            return;
        }
        if (a[i]==0){
            //如果当前物品能放进去
            if (maxWeight>currentWeight){
                currentValue += value[i];
                currentWeight += weight[i];
                a[i] = 1;
                //如果当前物品放进去后，此时最大价值达到最大
                if (currentValue> maxValue){
                    //更新最大的相关信息
                    maxValue = currentValue;
                    maxValuePath = a.clone();
                }
                Search(i+1,a);
            }else {
                Search(i-1,a);
            }
        }
        if (a[i]==1){
            a[i]=0;
            Search(i-1,a);
        }
    }
}
